Рис. 5.4. Поиск решения задачи с раскрашиванием карты на основе предварительной проверки. Вначале выполняется присваивание WA=red, затем предварительная проверка приводит к удалению значений red из областей определения соседних переменных NT и SA. После присваивания Q=green значение green удаляется из областей определения NT, SA и NSW. После присваивания V=blue из областей определения NSW и SA удаляется значение blue, в результате чего переменная SA остается без допустимых значений

Распространение ограничения

Хотя предварительная проверка обнаруживает много несовместимостей, она не позволяет обнаружить их все. Например, рассмотрим третью строку на рис. 5.4, которая показывает, что если переменная WA имеет значение red, a Q — green, то обеим переменным, NT и SA, должно быть присвоено значение blue. Но соответствующие им регионы являются смежными и поэтому не могут иметь одно и то же значение цвета. Предварительная проверка не позволяет обнаружить эту ситуацию как несовместимость, поскольку не предусматривает достаточно далекий просмотр наперед. Распространение ограничения (constraint propagation) — это общее название методов распространения на другие переменные последствий применения некоторого ограничения к одной переменной; в данном случае необходимо распространить ограничение с WA и Q на NT и SA (как было сделано с помощью предварительной проверки), а затем — на ограничение между NT и SA, чтобы обнаружить указанную несовместимость. К тому же желательно, чтобы такая операция выполнялась быстро: нет смысла ограничивать таким образом объем поиска, если будет расходоваться больше времени на распространение ограничений, чем на выполнение простого поиска.